/**
 * 单向链表源码
 */
#include <iostream>
#include <stdexcept>    // 抛出异常的头文件

#define eleType int

using namespace std;

/**
 * 存储各个节点的内容
 */
struct ListNode
{
    eleType data;   // 数据域
    ListNode *next; // 指针域
    ListNode(eleType x) : data(x), next(NULL) {}
};

/**
 * 链表类
 */
class LinkedList
{
private:
    ListNode *head;
    int size;

public:
    LinkedList() : head(NULL), size(0) {}
    ~LinkedList();

    // 增
    void insert(int nIndex, eleType element);

    // 删
    void remove(int nIndex);

    // 改
    void update(int nIndex, eleType element);

    // 查
    ListNode *find(eleType element);
    ListNode *get(int nIndex);

    // 打印
    void print();
};

LinkedList::~LinkedList()
{
    ListNode *pCurr = head;
    while (pCurr != NULL)
    {
        ListNode *pTemp = pCurr;
        pCurr = pCurr->next;
        delete pTemp;
    }
}

void LinkedList::insert(int nIndex, eleType element)
{
    // 判断插入的index值是否符合合理
    if (nIndex < 0 || nIndex > size)
    {
        throw std::out_of_range("Index position");
    }
    ListNode *newNode = new ListNode(element);
    if (nIndex == 0)
    {
        newNode->next = head;
        head = newNode;
    }
    else
    {
        ListNode *pCurr = head; // 游标指针，依次往后遍历，遍历到插入的前一个角标位置
        for (int j = 0; j < nIndex - 1; ++j)
        {
            pCurr = pCurr->next;
        }
        newNode->next = pCurr->next;
        pCurr->next = newNode;
    }
    size++;
}

void LinkedList::remove(int nIndex)
{
    if (nIndex < 0 || nIndex >= size)
    {
        throw std::out_of_range("Index position");
    }
    if (nIndex == 0)
    {
        ListNode *pTemp = head;
        head = pTemp->next;
        delete pTemp;
    }
    else
    {
        // 跟插入差不多思维，还是用游标指针，依次往后遍历，遍历到删除的前一个角标位置
        ListNode *pCurr = head;
        for (int j = 0; j < nIndex; ++j)
        {
            pCurr = pCurr->next;
        }
        ListNode *pTemp = pCurr->next; // 要删除的节点先存储一下
        pCurr->next = pTemp->next;     // 当前的节点指到删除节点的下一个节点
        delete pTemp;
    }

    size--;
}

void LinkedList::update(int nIndex, eleType element)
{  
    get(nIndex)->data = element;
}

ListNode *LinkedList::find(eleType element)
{
    ListNode *pTemp = head;
    for (int j = 0; j < size; ++j) 
    {
        if (pTemp->data == element) 
        {
            return pTemp;
        }
        pTemp = pTemp->next;
    }
    return NULL;
}

ListNode *LinkedList::get(int nIndex)
{
    if (nIndex < 0 || nIndex >= size)
    {
        throw std::out_of_range("Index position");
    }
    ListNode *pTemp = head;
    for (int j = 0; j < nIndex; ++j) 
    {
        pTemp = pTemp->next;
    }
    return pTemp;
}

void LinkedList::print() 
{
    ListNode *pTemp = head;
    while (pTemp)
    {
        cout << pTemp->data << " ";
        pTemp = pTemp->next;
    }
    cout << endl;
}
int main()
{
    // 测试一下
    LinkedList list;
    list.insert(0, 1);
    list.insert(1, 22);
    list.insert(2, 33);
    list.insert(3, 44);
    list.insert(4, 5);
    list.print();

    // 增
    list.insert(1, 99);
    list.print();

    // 删
    list.remove(2);
    list.print();
    
    // 改
    list.update(3, 100);
    list.print();

    // 查
    ListNode *p1 = list.find(100);
    cout << p1->data << endl;

    ListNode *p2 = list.get(4);
    cout << p2->data << endl;

    return 0;
}
/*输出结果如下
1 99 22 33 44 5 
1 99 22 44 5 
1 99 22 100 5 
100
5
 */